package code_capriccio;

import java.util.*;


// 代码随想录（递归回溯剪枝）

public class Demo11 {


    // LCR 080. 组合
    List<List<Integer>> ret;
    List<Integer> path;
    int n, k;
    public List<List<Integer>> combine(int _n, int _k) {
        ret = new ArrayList<>();
        path = new LinkedList<>();
        n = _n; k = _k;

        dfs(1);
        return ret;
    }
    private void dfs(int pos) {
        if(path.size() == k) {
            ret.add(new LinkedList<>(path));
            return;
        }

        for(int i = pos; i <= n; i++) {
            path.add(i);
            dfs(i + 1);
            path.remove(path.size() - 1);
        }
    }



    //LCR 081. 组合总和
    //List<List<Integer>> ret;
    //List<Integer> path;
    int target;
    public List<List<Integer>> combinationSum(int[] candidates, int _target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        target = _target;

        Arrays.sort(candidates);
        dfs(candidates, 0, 0);
        return ret;
    }
    private void dfs(int[] nums, int pos, int sum) {
        if(sum == target) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos; i < nums.length; i++) {
            if(sum + nums[i] > target) break;
            path.add(nums[i]);
            dfs(nums, i, sum + nums[i]);
            path.remove(path.size() - 1);
        }
    }



    //40. 组合总和 II
    //List<List<Integer>> ret;
    //List<Integer> path;
    boolean[] vis;
    //int n;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        n = candidates.length;
        vis = new boolean[n];

        Arrays.sort(candidates);
        dfs2(candidates, 0, target);
        return ret;
    }
    public void dfs2(int[] nums, int pos, int target) {
        if(target == 0) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos; i < n; i++) {      // 为了保证解集不重复，每次循环位置应从 pos 位置开始
            // 只有满足同一层没有使用过才可作为路径上的一个数
            if(!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1])) {
                if(target - nums[i] < 0) break;
                path.add(nums[i]);
                vis[i] = true;
                dfs2(nums, i + 1 ,target - nums[i]);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }




    //216. 组合总和 III
//    List<List<Integer>> ret;
//    List<Integer> path;
//    int k;
    public List<List<Integer>> combinationSum3(int _k, int n) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        k = _k;

        dfs3(1, 0, n);
        return ret;
    }
    private void dfs3(int pos, int count, int target) {
        if(count == k) {
            if(target == 0) ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos; i <= 9; i++) {
            if(target - i < 0) break;
            path.add(i);
            dfs3(i + 1, count + 1, target - i);
            path.remove(path.size() - 1);
        }
    }




    //17. 电话号码的字母组合
    List<String> ret2;
    StringBuffer path2;
    String[] flag =  new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        if(digits.length() == 0) return ret2;
        path2 = new StringBuffer();

        dfs(digits.toCharArray(), 0);
        return ret2;
    }
    private void dfs(char[] arr, int pos) {
        if(path2.length() == arr.length) {
            ret2.add(new String(path2));
            return;
        }

        for(int i = 0; i < flag[arr[pos]-'0'].length(); i++) {
            path2.append(flag[arr[pos]-'0'].charAt(i));
            dfs(arr, pos + 1);
            path2.deleteCharAt(path2.length() - 1);
        }
    }




    //131. 分割回文串
    List<List<String>> ret3;
    List<String> path3;
    public List<List<String>> partition(String _s) {
        // dp[i][j]: i ~ j 区间内的子串是否为回文子串
        int n = _s.length();
        char[] s = _s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--)
            for(int j = i; j < n; j++) {
                if(s[i] == s[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }

        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(s, 0, dp);
        return ret3;
    }
    private void dfs(char[] s, int pos, boolean[][] dp) {
        if(pos == s.length) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos; i < s.length; i++) {
            if(dp[pos][i]) {
                path3.add(new String(s, pos, i - pos + 1));
                dfs(s, i + 1, dp);
                path.remove(path.size() - 1);
            }
        }
    }




    //LCR 087. 复原 IP 地址
    List<String> ret4;
    public List<String> restoreIpAddresses(String s) {
        ret4 = new ArrayList<>();
        char[] arr = s.toCharArray();

        dfs(arr, 0 , 0, new StringBuilder());
        return ret4;
    }
    private void dfs(char[] s, int pos ,int count ,StringBuilder path) {
        if(count == 4) {
            if(pos == s.length) ret4.add(path.toString());
            return;
        }

        // 当前Ip地址可由 1 ~ 3位数字构成
        for(int i = 1; i <= 3; i++) {
            // 判断当前截取的子串是否超出数组范围
            if(pos + i - 1 >= s.length) break;
            String tmp = new String(s, pos, i);
            int num = Integer.parseInt(tmp);
            // 判断当前IP地址是否合法
            if(i == 1 || num >= Math.pow(10.0, i - 1) && num <= 255) {
                StringBuilder tmpPath = new StringBuilder(path);
                tmpPath.append(tmp);
                if(count < 3) tmpPath.append('.');
                dfs(s, pos + i, count + 1, tmpPath);
            }
        }
    }




    //78. 子集
//    List<List<Integer>> ret;
//    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();

        dfs2(nums, 0);
        return ret;
    }
    private void dfs2(int[] nums, int pos) {
        ret.add(new ArrayList<>(path));
        if(pos == nums.length) return;

        for(int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs2(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }



    //90. 子集 II
    //List<List<Integer>> ret;
    //List<Integer> path;
    //boolean[] vis;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        vis = new boolean[nums.length];

        Arrays.sort(nums);
        //dfs(nums, 0);
        return ret;
    }
    public void dfs(int[] nums, int pos) {
        ret.add(new ArrayList<>(path));
        if(pos == nums.length) return;

        for(int i = pos; i < nums.length; i++) {
            if(!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1])) {
                path.add(nums[i]);
                vis[i] = true;
                dfs(nums, i + 1);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }




    //491. 非递减子序列
//    List<List<Integer>> ret;
//    List<Integer> path;
//    public List<List<Integer>> findSubsequences(int[] nums) {
//        ret = new ArrayList<>();
//        path = new ArrayList<>();
//
//        dfs(nums, 0);
//        return ret;
//    }
//    public void dfs(int[] nums, int pos) {
//        if(path.size() > 1) ret.add(new ArrayList<>(path));
//        if(pos == nums.length) return;
//
//        int[] hash = new int[201];        // 对同一层元素进行去重
//        for(int i = pos; i < nums.length; i++) {
//            if(hash[nums[i] + 100] == 0 && (path.isEmpty() || nums[i] >= path.get(path.size() - 1))) {
//                path.add(nums[i]);
//                hash[nums[i] + 100]++;
//                dfs(nums, i + 1);
//                path.remove(path.size() - 1);
//            }
//        }
//    }




    //46. 全排列
//    List<List<Integer>> ret;
//    List<Integer> path;
//    boolean[] vis;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        vis = new boolean[nums.length];

        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums) {
        if(path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!vis[i]) {
                vis[i] = true;
                path.add(nums[i]);
                dfs(nums);
                vis[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }



    //47. 全排列 II
//    List<List<Integer>> ret;
//    List<Integer> path;
//    boolean[] vis;
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        Arrays.sort(nums);
//        ret = new ArrayList<>();
//        path = new ArrayList<>();
//        vis = new boolean[nums.length];
//
//        dfs(nums);
//        return ret;
//    }
//    public void dfs(int[] nums) {
//        if(path.size() == nums.length) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//
//        for(int i = 0; i < nums.length; i++) {
//            if(!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1])) {
//                vis[i] = true;
//                path.add(nums[i]);
//                dfs(nums);
//                vis[i] = false;
//                path.remove(path.size() - 1);
//            }
//        }
//    }





    //332. 重新安排行程







    //51. N 皇后
//    List<List<String>> ret;
//    List<String> path;
//    StringBuffer _tmp;
//    boolean[] col;      // 记录该列是否有皇后
//    boolean[] a;        // 记录正对角线是否有皇后
//    boolean[] b;        // 记录反对角线是否有皇后
//    public List<List<String>> solveNQueens(int n) {
//        ret = new ArrayList<>();
//        col = new boolean[n];
//        path = new ArrayList<>();
//        a = new boolean[n * 2];
//        b = new boolean[n * 2];
//        _tmp = new StringBuffer();
//        for(int i = 0; i < n; i++) _tmp.append('.');
//
//        dfs(n, 0);
//        return ret;
//    }
//    private void dfs(int n, int pos) {  //pos 记录当前行数
//        if(path.size() == n) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//
//        // i 表示当前所处的列
//        for(int i = 0; i < n; i++) {
//            if(col[i] == false && !a[i - pos + n] && !b[i + pos]) {
//                StringBuffer tmp = new StringBuffer(_tmp);
//                tmp.setCharAt(i, 'Q');
//                path.add(tmp.toString());
//                col[i] = true; a[i - pos + n] = true; b[i + pos] = true;
//                dfs(n, pos + 1);
//                path.remove(path.size() - 1);      // 恢复现场
//                col[i] = false; a[i - pos + n] = false; b[i + pos] = false;
//            }
//        }
//    }




    //36. 有效的数独
    public boolean isValidSudoku(char[][] board) {
        boolean[][] col = new boolean[9][10];
        boolean[][] row = new boolean[9][10];
        boolean[][][] cube = new boolean[3][3][10];

        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') continue;
                char ch = board[i][j];
                if(row[i][ch - '0'] || col[j][ch - '0'] || cube[i/3][j/3][ch - '0']) {
                    return false;
                } else {
                    row[i][ch - '0'] = col[j][ch - '0'] = cube[i/3][j/3][ch - '0'] = true;
                }
            }
        }

        return true;
    }



    //37. 解数独
//    boolean[][] col;
//    boolean[][] row;
//    boolean[][][] cube;
//    int count;
//    public void solveSudoku(char[][] board) {
//        col = new boolean[9][10];
//        row = new boolean[9][10];
//        cube = new boolean[3][3][10];
//
//        // 初始化
//        for(int i = 0; i < 9; i++) {
//            for(int j = 0; j < 9; j++) {
//                int num = board[i][j] - '0';
//                if(board[i][j] != '.')
//                    row[i][num] = col[j][num] = cube[i / 3][j / 3][num] = true;
//            }
//        }
//
//        dfs(board);
//    }
//    private boolean dfs(char[][] board) {
//        for(int i = 0; i < 9; i++) {
//            for(int j = 0; j < 9; j++) {
//                if(board[i][j] != '.') continue;
//
//                int k = 1;
//                for(; k <= 9; k++) {
//                    // 剪枝
//                    if(!row[i][k] && !col[j][k] && !cube[i/3][j/3][k]) {
//                        board[i][j] = (char) (k + '0');
//                        row[i][k] = col[j][k] = cube[i/3][j/3][k] = true;
//                        boolean flag = dfs(board);
//                        if(flag) return true;
//
//                        // 恢复现场
//                        row[i][k] = col[j][k] = cube[i/3][j/3][k] = false;
//                        board[i][j] = '.';
//                    }
//                }
//                if(k > 9) return false;
//            }
//        }
//        return true;
//    }

}
